package leetcode.pre50;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
 * <p>
 * 注意：
 * <p>
 * 答案中不可以包含重复的四元组。
 * <p>
 * 示例：
 * <p>
 * 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
 * <p>
 * 满足要求的四元组集合为：
 * [
 * [-1,  0, 0, 1],
 * [-2, -1, 1, 2],
 * [-2,  0, 0, 2]
 * ]
 * <p>
 * 其余见{@link leetcode.a_总结分布.Code11_N数之和}
 *
 * @date 2020/5/30 17:25
 */
public class Code18_FourNum_四数之和 {
    public static void main(String[] args) {
        int[] nums = {1, -2, -5, -4, -3, 3, 3, 5};
        int target = -11;
        fourSum(nums, target).forEach(System.out::println);
    }

    /**
     * 思路：同三数之和，三个指针。时间复杂度O(n³)
     */

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 3) {
            return res;
        }
        //先进行排序
        Arrays.sort(nums);
        int p3;
        int p4;
        //第一个数的位置位index。然后设定p1 = index+1,p2 = nums.length -1。
        //遍历判断是否有满足的数。
        for (int p1 = 0; p1 < nums.length - 3; p1++) {
            //TODO BUG,这里可能p1是-3， p2是-2，p3是-1,target < -3
//            if (nums[p1] > target) return res;
            //已经超出范围
            if (nums[p1] + nums[p1 + 1] + nums[p1 + 2] + nums[p1 + 3] > target) return res;
            //去重
            if (p1 != 0 && nums[p1] == nums[p1 - 1]) {
                continue;
            }
            for (int p2 = p1 + 1; p2 < nums.length - 2; p2++) {
                //去重
                if (p2 != p1 + 1 && nums[p2] == nums[p2 - 1]) {
                    continue;
                }
                p3 = p2 + 1;
                p4 = nums.length - 1;
                //不可用重复的数 ，left要小于right
                while (p3 < p4) {
                    int sum = nums[p1] + nums[p2] + nums[p3] + nums[p4];
                    if (sum == target) {
                        res.add(Arrays.asList(nums[p1], nums[p2], nums[p3], nums[p4]));
                        //【注意点2】去重，比如[....,-2,-2,....,2,2]。但是这个过程要L<R。否则当left = length-1,left +1 越界
                        while (p3 + 1 < nums.length && nums[p3] == nums[p3 + 1]) p3++;
                        while (p4 > 0 && nums[p4] == nums[p4 - 1]) p4--;
                        //left和right分别前后移动
                        p3++;
                        p4--;
                    } else if (sum < target) {
                        p3++;
                    } else {
                        p4--;
                    }
                }
            }
        }
        return res;
    }
}
